Several solutions exist for selecting the shortest path (or minimum defined cost) between selected nodes, even in a network having a large number of interconnected nodes. Computer programs known as “road-mapping” programs provide digital maps, often complete with detailed road networks down to the city-street level. Some road-mapping programs often employ variants of shortest path algorithms (wherein “shortest” means “least cost”). Among prominent algorithms that are often used to compute shortest paths, the Dijkstra algorithm finds the path with lowest cost (i.e., the shortest path) between a given source vertex (node) and every other vertex.
Many contemporary road-mapping programs use variations of the Dijkstra algorithm, including goal-directed search, in order to “guide” the shortest-path computation in the right general direction. Such variations typically involve estimating the weights of paths between intermediate locations and the destination. A good estimate reduces the number of locations and road segments that must be considered by the road-mapping program, resulting in a faster computation of shortest paths. A bad estimate can have the opposite effect, and increase the overall time required to compute shortest paths. Solutions based on the Dijkstra algorithm and other algorithms (such as A*) may often be modified to permit the inclusion of certain conditions relating to various criteria. For the purposes of giving driving directions, for instance, it might make sense to also include each intersection as a separate vertex of the graph. Although shortest paths can be generated for the quickest, shortest or preferred routes in consideration of certain criteria, computing the best route between locations may require significant computational time and resources.
It is also known to have road-mapping algorithms in which a large graph is split into smaller graphs, followed by pre-calculating the smaller graphs. Real-life graphs (e.g., graphs of streets of a country) are not easy to split so that the sub-graphs have little amount of external connections. In addition, keeping a hierarchy of multi-level sub-graphs requires several levels of splitting and is therefore quite a complicated process requiring its own splitting/pre-calculation resources. Such methods, therefore, have not proven effective for very large graphs.
The presently disclosed invention addresses these and other deficiencies in shortest path calculations and provides other advantages that are understood from the present disclosure.